#include "string_array.h"
#include <cstring>
#include <algorithm>
using namespace std;


myStr::myStr(const char* s){
    if(s == nullptr){
        length = 0;
        data = nullptr;
        next = nullptr;
        nextVal = nullptr;
        return;
    }

    length = static_cast<int>(strlen(s));
    data = new char[length + 1];
    memcpy(data, s, length + 1);

    next = new int[length];  
    nextVal = new int[length];
    for(int i = 0; i < length; ++i){  
        next[i] = -1;
        nextVal[i] = -1;
    }
}

myStr::~myStr(){
    if(data) delete [] data;
    if(next) delete [] next;
    if(nextVal) delete [] nextVal;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}


void myStr::kmp_next(){
    if(length <= 0) return;
    next[0] = -1;
    int k = -1;
    int i = 0;
    while(i < length - 1){
        if(k == -1 || data[i] == data[k]){
            ++i; ++k;
            next[i] = k;
        } else {
            k = next[k];
        }
    }
}


void myStr::kmp_nextVal(){
    if(length <= 0) return;
    kmp_next();
    nextVal[0] = -1;
    for(int i = 1; i < length; ++i){
        int j = next[i];
        if(j != -1 && data[i] == data[j])
            nextVal[i] = nextVal[j];
        else
            nextVal[i] = j;
    }
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << (next[i] + 1);
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << (nextVal[i] + 1);
    cout << endl;
}


int simpleMatch(const myStr& s, const myStr& pattern){
 
    if(pattern.length == 0) return 1;
    if(s.length < pattern.length) return -1;
    for(int i = 0; i <= s.length - pattern.length; ++i){
        int j = 0;
        for(; j < pattern.length; ++j){
            if(s.data[i + j] != pattern.data[j]) break;
        }
        if(j == pattern.length) return i + 1;
    }
    return -1;
}

int kmpMatch(const myStr& s, const myStr& pattern){

    if(pattern.length == 0) return 1;
    if(s.length < pattern.length) return -1;

    int m = pattern.length;
    int n = s.length;
    int* nextL = new int[m];
    nextL[0] = -1;
    int k = -1;
    int i = 0;
    while(i < m - 1){
        if(k == -1 || pattern.data[i] == pattern.data[k]){
            ++i; ++k; nextL[i] = k;
        } else k = nextL[k];
    }

    int si = 0, pi = 0;
    while(si < n && pi < m){
        if(pi == -1 || s.data[si] == pattern.data[pi]){ ++si; ++pi; }
        else pi = nextL[pi];
    }

    int res = (pi == m) ? (si - pi) + 1 : -1;
    delete [] nextL;
    return res;
}

bool replaceStr(myStr& s, const int& pos, const myStr& oldStr, const myStr& newStr){
    if(oldStr.length == 0) return false;
    int startIdx = pos - 1;
    if(startIdx < 0 || startIdx >= s.length) return false;
    myStr subS(s.data + startIdx); 
    int foundInSub = kmpMatch(subS, oldStr); 
    if(foundInSub < 0) return false;
    int usePos = startIdx + (foundInSub - 1);
    int newLen = s.length - oldStr.length + newStr.length;
    char* newData = new char[newLen + 1];
    if(usePos > 0) memcpy(newData, s.data, usePos);
    if(newStr.length > 0) memcpy(newData + usePos, newStr.data, newStr.length);
    int tailLen = s.length - (usePos + oldStr.length);
    if(tailLen > 0) memcpy(newData + usePos + newStr.length, s.data + usePos + oldStr.length, tailLen);
    newData[newLen] = '\0';
    if(s.data) delete [] s.data;
    s.data = newData;
    s.length = newLen;
    if(s.next) delete [] s.next;
    if(s.nextVal) delete [] s.nextVal;
    s.next = new int[max(1, s.length)];
    s.nextVal = new int[max(1, s.length)];
    for(int i = 0; i < s.length; ++i){ s.next[i] = -1; s.nextVal[i] = -1; }
    return true;
}


myMatrix::myMatrix(const int& r, const int& c, const int& n, const int* arr){
    rowNum = r;
    colNum = c;
    nodeNum = n;
    if(nodeNum > 0){
        nodeList = new matrixNode[nodeNum];
        for(int i = 0; i < nodeNum; ++i){
            nodeList[i].row = arr[3*i];
            nodeList[i].col = arr[3*i + 1];
            nodeList[i].value = arr[3*i + 2];
        }
    } else {
        nodeList = nullptr;
    }
}


myMatrix::myMatrix(){
    nodeList = nullptr;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
}

myMatrix::~myMatrix(){
    if(nodeList) delete [] nodeList;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

void myMatrix::FastTransposeSMatrix(myMatrix& b){
    b.rowNum = this->colNum;
    b.colNum = this->rowNum;
    b.nodeNum = this->nodeNum;

    if(b.nodeList) delete [] b.nodeList;
    if(nodeNum == 0){
        b.nodeList = nullptr;
        return;
    }

    b.nodeList = new matrixNode[nodeNum];
    int *colCounts = new int[colNum];
    for(int i = 0; i < colNum; ++i) colCounts[i] = 0;
    for(int i = 0; i < nodeNum; ++i) ++colCounts[nodeList[i].col];

    int *startingPos = new int[colNum];
    startingPos[0] = 0;
    for(int i = 1; i < colNum; ++i) startingPos[i] = startingPos[i-1] + colCounts[i-1];

    for(int i = 0; i < nodeNum; ++i){
        int col = nodeList[i].col;
        int pos = startingPos[col]++;
        b.nodeList[pos].row = nodeList[i].col;
        b.nodeList[pos].col = nodeList[i].row;
        b.nodeList[pos].value = nodeList[i].value;
    }

    delete [] colCounts;
    delete [] startingPos;
}